/*
    状压dp-上

    前置知识: 
    讲解003、讲解030、讲解031、讲解032、讲解033 - 位运算基础
    讲解043 - 根据数据量猜解法的技巧，天字第一号重要技巧
    讲解063 - 双向广搜
    讲解067 - 从递归入手二维动态规划
    【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

    本节课会讲述状压dp的原理以及4个题目，其中包括大名鼎鼎的TSP问题（题目4）

    下节课会见识更多状压dp问题 & 更多技巧

    注意：
    轮廓线dp是状压dp中一类比较难的问题，【扩展】课程阶段讲述
    插头dp是轮廓线dp中一类更难的问题，在笔试、面试中几乎没有出现的可能，不会安排。比赛同学自行学习

    ================================================

    状压dp
    设计一个整型可变参数status，利用status的位信息，来表示：
    某个样本是否还能使用，然后利用这个信息进行尝试
    写出尝试的递归函数 -> 记忆化搜索 -> 严格位置依赖的动态规划 -> 空间压缩等优化

    如果有k个样本，那么表示这些样本的状态，数量是2^k
    所以可变参数status的范围： 0 ~ (2^k)-1

    样本每增加一个，状态的数量是指数级增长的，所以状压dp能解决的问题往往样本数据量都不大
    一般样本数量在20个以内(10^6)，如果超过这个数量，计算量(指令条数)会超过 10^7 ~ 10^8
    讲解043 - 根据数据量猜解法的技巧，天字第一号重要技巧

    如果样本数量大到状压dp解决不了，或者任何动态规划都不可行，那么双向广搜是一个备选思路
    讲解063 - 双向广搜

    ================================================

    题目1
    我能赢吗
    给定两个整数n和m
    两个玩家可以轮流从公共整数池中抽取从1到n的整数（不放回）
    抽取的整数会累加起来（两个玩家都算）
    谁在自己的回合让累加和 >= m，谁获胜
    若先出手的玩家能稳赢则返回true，否则返回false
    假设两位玩家游戏时都绝顶聪明，可以全盘为自己打算
    测试链接 : https://leetcode.cn/problems/can-i-win/

    注意：这道题有两个可变参数status、rest
    但最关键的可变参数就1个，即status，表示还有哪些数字可以使用
    另一个可变参数rest是被status决定的，所以只需要对status做缓存表
    任何动态规划都是这样！只关注最关键的可变参数，被决定的可变参数不用管！不重要！

    ================================================

    题目2
    火柴拼正方形
    你将得到一个整数数组 matchsticks
    其中 matchsticks[i] 是第 i 个火柴棒的长度
    你要用 所有的火柴棍 拼成一个正方形
    你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次
    如果你能拼出正方形，则返回 true ，否则返回 false
    测试链接 : https://leetcode.cn/problems/matchsticks-to-square/

    ================================================

    题目3
    划分为k个相等的子集
    给定一个整数数组nums和一个正整数k，
    找出是否有可能把这个数组分成k个非空子集，其总和都相等
    测试链接 : https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/

    状压dp vs 纯暴力的递归结合剪枝（不做任何动态规划）

    状压dp：根据数据量进行复杂度的计算，发现可以通过，那就稳稳通过。推荐。因为能稳定通过。

    纯暴力的递归（不做任何动态规划）：根据数据量进行复杂度的计算，发现不能通过，但是有大量剪枝的策略，有可能在数据状况并不严苛的情况下能通过，甚至时间还比状压dp快，这是有可能的。但是如果出题人刻意设置数据状况，那么一定无法通过。不推荐。因为不能稳定通过，并且方法本身没什么亮点。

    ================================================

    题目4
    售货员的难题 - TSP问题
    某乡有n个村庄(1<=n<=20)，有一个售货员，他要到各个村庄去售货
    各村庄之间的路程s(1<=s<=1000)是已知的
    且A村到B村的路程，与B到A的路大多不同(有向带权图)
    为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，
    假设商店所在的村庄为1
    他不知道选择什么样的路线才能使所走的路程最短
    请你帮他选择一条最短的路
    测试链接 : https://www.luogu.com.cn/problem/P1171

*/